\section{Model and problem statement}
\label{sec:pre}
In this section, we formally define our problem and models.  

\smallskip
{\noindent {\sl The $k$-gossip problem.}} In this problem, $k$
different tokens are assigned to a set $V$ of $n \ge k$ nodes, where
each node may have any subset of the tokens, and the goal is to
disseminate all the $k$ tokens to all the nodes.

\smallskip
{\noindent {\sl The online model.}}  Our online model is the
worst-case adversarial model of~\cite{kuhn+lo:dynamic}.  Nodes
communicate with each other using anonymous broadcast in synchronized
rounds.  At the beginning of round $r$, each node in $V$ decides what
message to broadcast based on its internal state and coin tosses (for
a randomized algorithm); the adversary chooses the set of edges that
forms the communication network $G_r$ over $V$ for round $r$.  We
adopt a {\em strong adversary}\/ model in which the adversary, at the time
of constructing $G_r$, knows the outcomes of the random coin tosses
used by the algorithm in round $r$ but is unaware of any randomness
used by the algorithm in future rounds.  The only constraint on $G_r$
is that it be connected; this is the same as the $1$-interval
connectivity model of~\cite{kuhn+lo:dynamic}.

The above model is equivalent to the adversary knowing the messages to
be sent in round $r$ before choosing the edges for round $r$.  We do
not place any bound on the size of the messages, our lower bound
simply requires each message to contain at most one token.  Finally,
we note that under the strong adversary model, there is a distinction
between randomized algorithms and deterministic algorithms since a
randomized algorithm may be able to exploit the fact that in any round
$r$, while the adversary is aware of the randomness used in that
round, it does not know the outcomes of any randomness used in
subsequent rounds.

\smallskip
{\noindent {\sl The offline model.}} In the offline model, we are
given a sequence of networks $\langle G_r \rangle$ where $G_r$ is a
connected communication network for round $r$.  In each round at most
one token is broadcast by any node.  It can be easily seen that the
$k$-gossip problem can be solved in $nk$ rounds in the offline model;
so we may assume that the given sequence of networks is of length at
most $nk$.

\smallskip
{\noindent {\sl Token-forwarding algorithms.}} Informally, a
token-forwarding algorithm is one that does not combine or alter
tokens, only stores and forwards them.  Formally, we call an algorithm
for $k$-gossip a token-forwarding algorithm if for every node $v$,
token $t$, and round $r$, $v$ contains $t$ at the start of round $r$
of the algorithm if and only if either $v$ has $t$ at the start of the
algorithm or $v$ received a message containing $t$ prior to round $r$.

Finally, several of our arguments are probabilistic.  We use the term
``with high probability'' to mean with probability at least $1 -
1/n^c$, for a constant $c$ that can be made sufficiently high by
adjusting related constant parameters.

\junk{
\begin{problem}[$k$-token dissemination]
\label{prob:ktoken}
\end{problem}

We assume synchronized communication between nodes, and the message
size is $O(\log n)$ where $n$ is the number of nodes in the graph. The
dynamic graphs are provided by adversaries. We consider the following
3 kinds of adversaries.
\begin{enumerate}
\item {\sc Strong Adversary}: At each round of communication, each
  node decides which token to send first. The adversary knows which
  node is going to send which token and the set of tokens each node
  has, and then the adversary provides a connected graph as the
  communication graph.
\item {\sc Weak Adversary}: At each round of communication, the
  adversary provides a connected graph as the communication graph
  first. Each node knows who are his neighbors, and then decides which
  token to send. The adversary knows the set of tokens each node has
  at any time.
\item {\sc Oblivious Adversary}: Before the token dissemination
  process starts, the adversary has to provide a sequence of graphs
  for all rounds of communications. 
\end{enumerate}
}
